/*
 * @lc app=leetcode.cn id=236 lang=cpp
 *
 * [236] 二叉树的最近公共祖先
 * 2、该树为二叉树，结点中有指向父结点的指针
 * 有了父结点，就可以找到任意结点到根结点的路径；因此：
 * 分别找到从两个结点开始到根结点的路径，即两个链表；
 * 然后找到两个链表的第一个公共结点，就是最低的公共父结点；
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

/*
class Solution
{
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
  {
    if (nullptr == root) return nullptr;  // 空节点返回空指针 递归出口1

    if (p == root || q == root) return root;  // 递归出口2

    // 找左子树中是否存在p或q
    TreeNode* left = lowestCommonAncestor(root->left, p, q);  // 存在时返回p或q，不存在时返回nullptr

    // 找右子树是否存在p或q
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // p, q存在于root的左子树与右子树中
    if (left && right)
      return root;  // left和right分别有p或q,则其父结点root为p,q的最低公共祖先

    else
    {
      // left和right不是都有的情况
      // 1.若left存在，说明p, q在root的左子树中
      // 2.否则right存在，说明p,q在root的右子树中
      // 不会出现left,right都不存在的结果，因为题目假设p,q在树中
      /// 1.2.都是返回先找到的节点(p,q任意)即为自己的公共祖先
      return left ? left : right;
    }
  }
};
/*


/*
改进：在找完左子树的共同父节点时如果结果存在，且不是p或q，
那么不用再找右子树了，直接返回这个结果即可，同理，对找完右子树的结果做同样处理，参见代码如下：
*/
class Solution
{
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
  {
    if (nullptr == root) return nullptr;  // 空节点返回空指针 递归出口1

    if (p == root || q == root) return root;  // 递归出口2

    // 找左子树中是否存在p或q
    TreeNode* left = lowestCommonAncestor(root->left, p, q);

    // 如果left不为空且不是p或q,则其为公共祖先,
    // left此时指向left与right的公共祖先root,应该是p，q分别位于
    if (left && left != p && left != q) return left;  // 针对递归出口3吗？

    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (right && right != p && right != q) return right;

    if (left && right)  // 递归出口3，left和right分别有p或q,则其父结点root为p,q的最低公共祖先
      return root;
    else
      return left ? left : right;
  }
};

// @lc code=end
